//#include <bits/stdc++.h>
#include "head.h"

using namespace std;
using ll = long long;

void solve()
{
    ll k, l1, r1, l2, r2;
    cin >> k >> l1 >> r1 >> l2 >> r2;
    ll n = 1, ans = 0;
    while (n <= r2)
    {
        ll lx = max(l1, (l2 + n - 1) / n), rx = min(r1, r2 / n);
        ans += max(0LL, rx - lx + 1);
        n *= k;
    }
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}